package hot100.logos81To90;

/**
 * @author logos
 * date 2025/7/18 19:07
 * @version v1.0
 * @Package hot100.logos81To90
 */
public class logos90 {

    /**
     * 90. 最长有效括号
     * https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int longestValidParentheses(String str) {
            char[] s = str.toCharArray();
            int[] dp = new int[s.length];
            int ans = 0;
            for (int i = 1, p; i < s.length; i++) {
                if (s[i] == ')') {
                    p = i - dp[i - 1] - 1;
                    if (p >= 0 && s[p] == '(') {
                        dp[i] = dp[i - 1] + 2 + (p > 0 ? dp[p - 1] : 0);
                    }
                }
                ans = Math.max(dp[i], ans);
            }
            return ans;
        }
    }
}
